/**
 *给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 *堆排序
 *https://leetcode.cn/problems/7WHec2/
 */
class SortListDuiSort {
    public ListNode sortList(ListNode head) {
        if(head==null){
            return null;
        }
        int[] arr=new int[200000];
        ListNode cur=head;
        int len=0;
        int i=1;
        while(cur!=null){
            arr[i]=cur.val;
            cur=cur.next;
            i++;
        }
        cur=head;
        for(i=len/2;i>0;i--){
            HeapAdjust(arr,i,len);
        }
        for(i=len;i>1;i--){
            swap(arr,1,i);
            HeapAdjust(arr,1,i-1);
        }
        cur=head;
        for(i=1;i<=len&&cur!=null;i++){
            cur.val=arr[i];
            cur=cur.next;
        }
        return head;
    }
    public void HeapAdjust(int[] arr,int s,int m){
        int temp=arr[s];
        int j=0;
        for(j=2*s;j<=m;j*=2){
            if(j<m&&arr[j]<arr[j+1]){
                j++;
            }
            if(temp>=arr[j]){
                break;
            }
            arr[s]=arr[j];
            s=j;
        }
        arr[s]=temp;
    }
    public void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}